package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array/">检查数组是否存在有效划分(Check if There is a Valid Partition For The Array)</a>
 * <p>给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个 连续 子数组。</p>
 * <p>
 * 如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分：
 *     <ol>
 *         <li>子数组 恰 由 2 个相等元素组成，例如，子数组 [2,2] 。</li>
 *         <li>子数组 恰 由 3 个相等元素组成，例如，子数组 [4,4,4] 。</li>
 *         <li>子数组 恰 由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。</li>
 *     </ol>
 * </p>
 * <p>如果数组 至少 存在一种有效划分，返回 true ，否则，返回 false 。</p>
 * <p>
 * <pre>
 * 示例 1：
 *      输入：nums = [4,4,4,5,6]
 *      输出：true
 *      解释：数组可以划分成子数组 [4,4] 和 [4,5,6] 。
 *      这是一种有效划分，所以返回 true 。
 *
 * 示例 2：
 *      输入：nums = [1,1,1,2]
 *      输出：false
 *      解释：该数组不存在有效划分。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>2 <= nums.length <= 10^5</li>
 *     <li>1 <= nums[i] <= 10^6</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/1 9:12
 */
public class LC2369CheckIfThereIsValidPartitionForTheArray {

    static class Solution {
        public boolean validPartition(int[] nums) {
            int n = nums.length;
            boolean[] dp = new boolean[n + 1];
            dp[0] = true;
            for (int i = 1; i <= n; i++) {
                if (i >= 2) {
                    dp[i] = dp[i - 2] && validTwo(nums[i - 2], nums[i - 1]);
                }
                if (i >= 3) {
                    dp[i] = dp[i] || (dp[i - 3] && validThree(nums[i - 3], nums[i - 2], nums[i - 1]));
                }
            }
            return dp[n];
        }

        private boolean validTwo(int num1, int num2) {
            return num1 == num2;
        }

        private boolean validThree(int num1, int num2, int num3) {
            return (num1 == num2 && num1 == num3) || (num1 + 1 == num2 && num1 + 2 == num3);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.validPartition(new int[]{4, 4, 4, 5, 6}));
        System.out.println(solution.validPartition(new int[]{1, 1, 1, 2}));
    }
}
